package sword_offer;

import java.util.*;

/**
 * @ClassName _38PermutationString
 * @Description: 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 *  
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。（重复这个点需要特别考虑）
 *
 *  
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *  
 *
 * 限制：
 *
 * 1 <= s 的长度 <= 8
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 10:25
 */
public class _38PermutationString {
    public static void main(String[] args) {
//        String s = "abcd";
//        String s = "aad";
        String s = "axxx";

        String[] permutationImprove = new _38PermutationString().permutation(s);
        System.out.println(Arrays.toString(permutationImprove));
    }
    List<String> result = new LinkedList<>();
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();// 熟悉这几个API，字符串转数组
        traceback(chars,0);

        return result.toArray(new String[result.size()]);// list转数组
    }

    public void traceback(char[] chars, int index){
        if (index == chars.length){
            result.add(String.valueOf(chars));
            return;
        }
        // 创建set集合，记录该位置上遍历过的元素
        Set<Character> visited = new HashSet<>();
        for (int i = index; i < chars.length; i++) {
            if (visited.contains(chars[i]))
                continue;
            visited.add(chars[i]);
            swap(chars, i, index);
            traceback(chars, index + 1);
            swap(chars, i, index);
        }
    }

    public void swap(char[] chars, int a, int b){
        char temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

}
